package f_graph_basics.c_graph_component;

import f_graph_basics.a_graph_representation.Graph;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 通过一个图对象
 * 使用深度优先的递归遍历
 * 构造出这个图的扫描对象
 * 可以知道
 * 1. 图包含多少连通分量c - 每两个不同的连通分量之间无法互通
 * 2. 可以直接知道任意点之间是否相连
 */
public class GraphScan {
    private Graph g; // 图的副本
    private int[] visited; // 0 - 未访问过 1 - 访问过
    public int ccount; // 联通分量的个数
    private int[] id;// 图中各点id - 如果相连通，分配统一id

    /**
     * 分析图的连通性
     * @param g
     */
    public GraphScan(Graph g) {
        this.g = g;
        this.ccount = 0;
        visited = new int[g.v()];
        id = new int[g.v()];
        Arrays.fill(id, -1);
        for (int i = 0; i < g.v(); i++) {
            if (visited[i] != 1) {
                dfs(i); // 对i所在的连通分量进行深度优先遍历
                ccount++; // 连通分量加1
            }
        }
    }

    // 递归
    // 对顶点v进行深度优先遍历
    private void dfs(int v) {
        visited[v] = 1;
        id[v] = ccount;
        ArrayList<Integer> edges = g.getEdgesByVertex(v);
        for (int e : edges) {
            if (visited[e] != 1) {
                dfs(e);
            }
        }
    }

    /**
     * 判断v和w两个顶点是否连通
     * @param v
     * @param w
     * @return
     */
    public boolean isConnected(int v, int w) {
        assert w >= 0 && w < g.v();
        assert v >= 0 && v < g.v();
        return id[v] == id[w];
    }
}
